// 11.4 无序容器
/**
 * 新标准定义了4个无序关联容器（unordered associative container）。这些容器不是使用比较运算符来组织元素，
 * 而是使用一个哈希函数（hash function）和关键字类型的==运算符。
 * 如果关键字类型固有就是无序的，或者性能测试发现问题可以用哈希技术解决，就可以使用无序容器。
 */

#include <iterator>
#include <vector>
#include <list>
#include <deque>
#include <forward_list>
#include <string>
#include <array>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
using std::swap;
using std::vector, std::list, std::deque, std::forward_list, std::string, std::array, std::stack, std::queue;
#include "../Chapter07/Sales_data.h"
#include <iostream>
using std::begin, std::cbegin, std::end, std::cend, std::find, std::accumulate, std::equal, std::fill, std::fill_n, std::back_inserter;
using std::cin, std::cout, std::endl;
using std::copy, std::replace, std::replace_copy;
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <utility>
using namespace std;

size_t hasher(const Sales_data &sd)
{
    return hash<string>()(sd.isbn());
}

bool eqOp(const Sales_data &lhs, const Sales_data &rhs)
{
    return lhs.isbn() == rhs.isbn();
}

int main()
{
    // 使用无序容器
    // 除了哈希管理操作之外，无序容器还提供了与有序容器相同的操作（find、insert等）。
    // 这意味着我们曾用于map和set的操作也能用于unordered_map和unordered_set。类似的，无序容器也有允许重复关键字的版本。

    // 管理桶
    // 无序容器的性能依赖于哈希函数的质量和桶的数量和大小
    // 无序容器提供了一组管理桶的函数，如表11.8所示。这些成员函数允许我们查询容器的状态以及在必要时强制容器进行重组。[插图]
    // 桶接口
    // 1. c.bucket_count() 正在使用的桶的数目
    // 2. c.max_bucket_count() 容器能容纳的最多的桶的数量
    // 3. c.bucket_size(n) 第n个桶中有多少个元素
    // 4. c.bucket(k) 关键字为k的元素在哪个桶中
    // 桶迭代
    // 1. local_iterator 可以用来访问桶中元素的迭代器类型
    // 2. const_local_iterator 桶迭代器的const版本
    // 3. c.begin(n), c.end(n) 桶n的首元素迭代器与尾后迭代器
    // 4. c.cbegin(n), c.cend(n) 与前两个函数类似，但返回const_local_iterator
    // 哈希策略
    // 1. c.load_factor() 每个桶的平均元素数量，返回float值
    // 2. c.max_load_factor() c试图维护的平均桶大小，返回float值。c会在需要时添加新的桶，以使得load_factor<=max_load_factor重组存储
    // 3. c.rehash(n) 重组存储，使得bucket_count>=n且bucket_count>size/max_load_factor
    // 4. c.reserve(n) 重组存储，使得c可以保存n个元素且不必rehash

    // 无序容器对关键字类型的要求
    // 默认情况下，无序容器使用关键字类型的==运算符来比较元素
    // 我们不能直接定义关键字类型为自定义类类型的无序容器。与容器不同，不能直接使用哈希模板，而必须提供我们自己的hash模板版本。
    // 我们不使用默认的hash，而是使用另一种方法，类似于为有序容器重载关键字类型的默认比较操作（参见11.2.2节，第378页）。
    using SD_multiset = unordered_multiset<Sales_data,decltype(hasher)*,decltype(eqOp)*>;
    SD_multiset bookstore(42,hasher,eqOp); // 参数是桶大小、哈希函数指针、相等判断运算符指针

    return 0;
}